#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


typedef pair<int, int> PII;


class point_t {
public:
    point_t (int a, int t): n(a), type(t){}
    int n;
    int type;
};

bool myComp(const point_t &lhs, const point_t &rhs)
{
    return lhs.n <= rhs.n;
}


int main(int argc, char **argv)
{
    vector<PII> points;
    vector<point_t> dots;

    for (int i = 0; i < 20; i++) {
        int start = rand()%100;
        int end = rand()%100;
        if (start < end) points.push_back(make_pair(start, end));
        else if (end < start)  points.push_back(make_pair(end, start));
    }
    sort(points.begin(), points.end());
    for (int i = 0; i < points.size(); i++) {
        cout << i << ": " << points[i].first << " " << points[i].second << endl;
        dots.push_back(point_t( points[i].first, 0));
        dots.push_back(point_t( points[i].second, 1));
    }
    sort(dots.begin(), dots.end(), myComp);
    for (int i = 0; i < dots.size(); i++)
        cout << dots[i].n << " " << dots[i].type << endl;

    map<pair<int, int>, vector<int> > myMap;
    for (int i = 1; i < dots.size(); i++) {
        if (dots[i].n == dots[i-1].n) continue;
        PII range = make_pair(dots[i-1].n, dots[i].n);
        for (int j = 0; j < points.size(); j++) {
            if ((points[j].first <=  dots[i-1].n && points[j].second >=  dots[i].n)) {
                cout << "Get it" << endl;
                myMap[range].push_back(j);
            }
        }
    }

    for (map<pair<int, int>, vector<int> >::iterator iter = myMap.begin(); iter != myMap.end(); iter++) {
        cout << iter->first.first << " " << iter->first.second << ":" ;
        for (int i = 0; i < iter->second.size(); i++) {
            cout << "(" << points[ iter->second[i]].first << " " <<  points[ iter->second[i]].second << ")" <<" ";
        }
        cout << endl;
    }

    while(1) {
        int a;
        cout << "please input the point: " << endl;
        cin >> a;
        map<pair<int, int>, vector<int> >::iterator low;
        low = myMap.upper_bound(make_pair(a-1, a));
        cout << low->first.first << " " << low->first.second << endl;
    }


}
